package com.xk._02算法篇._01sort.sort.cmp;

import com.xk._02算法篇._01sort.sort.Sort;
import com.xk.tools.Integers;

import java.util.LinkedList;
import java.util.List;

/**
 * @description: 希尔排序
 * @author: xu
 * @date: 2022/10/2 10:43
 */
public class ShellSort2<E extends Comparable<E>> extends Sort<E> {

    /**
     * 希尔排序
     */
    private void shellSort(){
        List<Integer> stepSequence = shellStepSequence();
        for (Integer step : stepSequence) {
            shellSort(step);
        }
    }

    /**
     * 分成step列进行排序
     * @param step
     */
    private void shellSort(int step) {
        // col: 第几列
        for (int col = 0; col < step; col++) { // 对第col列进行排序
            // 对 [0, array.length) 范围的元素进行插入元素
            // col、col+step、col+2*step、col+3*step......
            for (int row = col + step; row < array.length; row += step) {
                int curIndex = row;
                while (curIndex > col && cmp(curIndex - step, curIndex) > 0) {
                    swap(curIndex, curIndex - step);
                    curIndex -= step;
                }
            }
        }
    }

    private List<Integer> shellStepSequence() {
        List<Integer> stepSequence = new LinkedList<>();
        int k = 0, step = 0;
        while (true) {
            if (k % 2 == 0) {
                int pow = (int) Math.pow(2, k >> 1);
                step = 1 + 9 * (pow * pow - pow);
            } else {
                int pow1 = (int) Math.pow(2, (k - 1) >> 1);
                int pow2 = (int) Math.pow(2, (k + 1) >> 1);
                step = 1 + 8 * pow1 * pow2 - 6 * pow2;
            }
            if (step >= array.length) break;
            stepSequence.add(0, step);
            k++;
        }
        return stepSequence;
    }

    @Override
    protected void sort() {
        shellSort();
    }

    public static void main(String[] args) {
        Integer[] array = Integers.random(32, 1, 100);
        Integers.println(array);

        Sort<Integer> mergeSort = new ShellSort2<>();
        mergeSort.sort(array);
        Integers.println(array);
        System.out.println(mergeSort);
    }
}
